/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/5/21 20:17
 */
// 搜索旋转排序数组
// 数组中的每个值都独一无二
    // 将数组一分为二，其中一定有一个有序，另一个可能有序也可能部分有序
    // 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
    //33-查找旋转数组不重复；81-查找旋转数组可重复复；153-旋转数组最小值不重复；
    //154旋转数字最小值重复，这几个一起做做，二分的题目太难太细节，需要对比
public class Solution33 {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 如果中间的数小于最右边的数，则右半段有序
            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            // 若中间数大于最右边数，则左边有序
            else {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
        }
        return -1;
    }
}
